#ifndef TRIE_H_
#define TRIE_H_

#include <algorithm>
#include <cstddef>
#include <unordered_map>
#include <vector>
#include <winscard.h>


namespace lxj
{
// 构建前缀和数组。快速解决子数组范围求和问题
class NumArray {
    inline static int arr[10001]{0};
    int               len;

public:
    NumArray(std::vector<int>& nums)
    {
        len    = nums.size();
        arr[0] = 0;
        for (int i = 1; i <= len; i++) {
            arr[i] = arr[i - 1] + nums[i - 1];
        }
    }

    ~NumArray()
    {
        for (int i = 1; i <= len; i++) {
            arr[i] = 0;
        }
    }

    int sumRange(int left, int right) { return arr[right + 1] - arr[left]; }
};

// 返回无序数组中累加和为给定值的最长子数组长度
// 给定一个无序数组arr, 其中元素可正、可负、可0
// 给定一个整数aim
// 求arr所有子数组中累加和为aim的最长子数组长度
// 测试链接 : https://www.nowcoder.com/practice/36fb0fd3c656480c92b569258a1223d5
inline int LongestSubarraySumEqualsAim(int* arr, size_t len, int aim)
{
    std::unordered_map<int, int> map;
    map[0]  = -1;
    int ans = 0;
    for (int i = 0, sum = 0; i < len; i++) {
        sum += arr[i];
        if (map.count(sum - aim) != 0) {
            ans = ans > i - map[sum - aim] ? ans : i - map[sum - aim];
        }
        if (map.count(sum) == 0) {
            map[sum] = i;
        }
    }
    return ans;
}

// 返回无序数组中累加和为给定值的子数组个数
// 测试链接 : https://leetcode.cn/problems/subarray-sum-equals-k/
inline int subarraySum(std::vector<int>& nums, int k)
{
    std::unordered_map<int, int> map;
    map[0]  = 1;
    int ans = 0;
    for (int i = 0, sum = 0; i < nums.size(); i++) {
        sum += nums[i];
        ans += map.count(sum - k) == 0 ? 0 : map[sum - k];
        map[sum] += 1;
    }
    return ans;
}


// 返回无序数组中正数和负数个数相等的最长子数组长度
// 给定一个无序数组arr，其中元素可正、可负、可0
// 求arr所有子数组中正数与负数个数相等的最长子数组的长度
// 测试链接 : https://www.nowcoder.com/practice/545544c060804eceaed0bb84fcd992fb
inline int subarraySamePosiNagaNumber(int* arr, size_t len)
{
    std::vector<int> tmp(len, 0);
    for (int i = 0; i < len; i++) {
        tmp[i] = arr[i] == 0 ? 0 : arr[i] > 0 ? 1 : -1;
    }
    return LongestSubarraySumEqualsAim(tmp.data(), len, 0);
}

// 表现良好的最长时间段
// 给你一份工作时间表 hours，上面记录着某一位员工每天的工作小时数
// 我们认为当员工一天中的工作小时数大于 8 小时的时候，那么这一天就是 劳累的一天
// 所谓 表现良好的时间段 ，意味在这段时间内，「劳累的天数」是严格 大于 不劳累的天数
// 请你返回 表现良好时间段 的最大长度
// 测试链接 : https://leetcode.cn/problems/longest-well-performing-interval/
inline int longestWPI(std::vector<int>& hours)
{
    std::unordered_map<int, int> map;
    map[0]  = -1;
    int ans = 0;
    for (int i = 0, sum = 0; i < hours.size(); i++) {
        sum += hours[i] > 8 ? 1 : -1;
        if (sum > 0) {
            ans = i + 1;
        }
        else {
            if (map.count(sum - 1) != 0) {
                ans = ans > i - map[sum - 1] ? ans : i - map[sum - 1];
            }
        }
        map.count(sum) == 0 ? map[sum] = i : (int)0;
    }
    return ans;
}

// 使数组和能被P整除
// 给你一个正整数数组 nums，请你移除 最短 子数组（可以为 空）
// 使得剩余元素的 和 能被 p 整除。 不允许 将整个数组都移除。
// 请你返回你需要移除的最短子数组的长度，如果无法满足题目要求，返回 -1 。
// 子数组 定义为原数组中连续的一组元素。
// 测试链接 : https://leetcode.cn/problems/make-sum-divisible-by-p/
inline int minSubarray(std::vector<int>& nums, int p)
{
    int mod = 0;
    for (auto i : nums) {
        mod = (mod + i) % p;
    }
    if (mod == 0) return 0;

    std::unordered_map<int, int> map;
    map[0]  = -1;
    int ans = ~(1 << 31);
    for (int i = 0, cur = 0, find; i < nums.size(); i++) {
        cur  = (cur + nums[i]) % p;
        find = (cur + p - mod) % p;
        if (map.count(find)) {
            ans = ans < i - map[find] ? ans : i - map[find];
        }
        map[cur] = i;
    }
    return ans == nums.size() ? -1 : ans;
}

// 每个元音包含偶数次的最长子字符串
// 给你一个字符串 s ，请你返回满足以下条件的最长子字符串的长度
// 每个元音字母，即 'a'，'e'，'i'，'o'，'u'
// 在子字符串中都恰好出现了偶数次。
// 测试链接 :
// https://leetcode.cn/problems/find-the-longest-substring-containing-vowels-in-even-counts/
inline int findTheLongestSubstring(std::string s)
{
    auto move = [](char c) {
        switch (c) {
        case 'a': return 0;
        case 'e': return 1;
        case 'i': return 2;
        case 'o': return 3;
        case 'u': return 4;
        }
        return -1;
    };
    int  len = s.size();
    int* map = new int[32];
    std::fill(map, map + 32, -2);
    map[0]  = -1;
    int ans = 0;
    for (int i = 0, status = 0, m; i < len; i++) {
        m = move(s[i]);
        m == -1 ? (int)0 : status ^= 1 << m;
        if (map[status] != -2) {
            ans = ans > i - map[status] ? ans : i - map[status];
        }
        else {
            map[status] = i;
        }
    }
    delete[] map;
    return ans;
}

}   // namespace lxj

#endif
